package countingsort;

/**
 * @ClassName CountingSort
 * @Description 计数排序 用于 指定范围的数据  稳定的
 * @Author ZJX
 * @Date 2024/9/10 18:12
 * @Version 1.0
 */

/**
 * 计数排序的特性总结：
 * 1. 计数排序在数据范围集中时，效率很高，但适用范围及场景有限。
 * 2. 时间复杂度：O(MAX(N, 范围))，其中 N 是数组长度，范围是数组中的数据范围（最大值 - 最小值）。
 * 3. 空间复杂度：O(范围)，需要额外的计数数组来记录每个数字出现的次数。
 * 4. 稳定性：稳定排序，保持相同元素的相对位置不变。
 */

public class CountingSort {
    public static void countsort(int[] arr){
        int max = arr[0];
        int min = arr[0];

//        循环找到数组中最大值与最小值
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
            if (arr[i] < min){
                min = arr[i];
            }
        }

//        计数数组存放着每个数据出现的次数
        int[] count = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;
        }

        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0){
                arr[index++] = i + min;
                count[i]--;
            }
        }

    }
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1, 7, 9, 5};
        countsort(arr);
        System.out.println("排序后的数组: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
